package Tree;

public class 最大二叉树 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return findNode(nums, 0, nums.length);
    }

    private TreeNode findNode(int[] nums, int begin, int end) {
        if (begin >= end) return null;
        if (end - begin == 1) return new TreeNode(nums[begin]);
        int rootIndex = begin;
        for (int i = begin + 1; i < end; i++) if (nums[rootIndex] < nums[i]) rootIndex = i;
        TreeNode root = new TreeNode(nums[rootIndex]);
        root.left = findNode(nums, begin, rootIndex);
        root.right = findNode(nums, rootIndex + 1, end);
        return root;
    }
}
